package com.mlh.dp.背包问题.a01背包;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/4/19 10:40
 * @DESCRIPTION
 */

// 给你一个非负整数数组 nums 和一个整数 target 。
// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
public class 目标和 {
    public  int method1(int[] nums, int target) {
        int total=0;
        for (int i = 0; i < nums.length; i++) {
            total+=nums[i];
        }
        //如果target的绝对值大于total，那么是没有方案的
        if (Math.abs(target) > total) return 0;
        //如果(target+sum)除以2的余数不为0，也是没有方案的
        if ((target + total) % 2 == 1) return 0;

        int value=(target+total)/2;
        int[] dp = new int[value + 1];
        dp[0]=1;//这里要初始化为1，想想也是，如果dp[j-nums[i]]=0时，就是一种方法，如果dp[0]=0的话这种方法就没法加上去
        for (int i = 0; i < nums.length; i++) {
            for (int j = value; j >=nums[i] ; j--) {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[value];
    }

    @Test
    public void test(){
        method1(new int[]{1,1,1,1,1},3);
    }
    //解题思路
    //假设加法的总和为x，那么减法对应的总和就是sum - x。
    // 所以我们要求的是 x - (sum - x) = target
    // x = (target + sum) / 2
    // 此时问题就转化为，用nums装满容量为x的背包，有几种方法。
    public int practice(int[] nums, int target) {
        int sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
        }
        if(Math.abs(target)>sum||(sum+target)%2!=0){//x计算出来存在小数，肯定就不可能把这个背包装满
            return 0;
        }
        int bagSize=(sum+target)/2;
        int[] dp=new int[bagSize+1];
        dp[0]=1;//初始化
        for (int i = 0; i < nums.length; i++) {
            for (int j = (sum+target)/2; j >=nums[i] ; j--) {
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }
}
